package a00_LeetCode.Tree;

/**
 * @Author quan
 * @Description 填充每个节点的下一个右侧节点指针
 * 给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
 * @Date 2023/4/2 16:08
 */
public class Num116_connect {
    public Node connect(Node root) {
        traverse(root.left,root.right);
        return root;
    }

    private void traverse(Node leftNode, Node rightNode) {
        if(leftNode == null){
            return;
        }
        leftNode.next = rightNode;
        traverse(leftNode.left,leftNode.right);
        traverse(leftNode.right,rightNode.left);
        traverse(rightNode.left,rightNode.right);
    }
}

// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
